/*
 *    GeoTools - The Open Source Java GIS Toolkit
 *    http://geotools.org
 *
 *    (C) 2002-2008, Open Source Geospatial Foundation (OSGeo)
 *
 *    This library is free software; you can redistribute it and/or
 *    modify it under the terms of the GNU Lesser General Public
 *    License as published by the Free Software Foundation;
 *    version 2.1 of the License.
 *
 *    This library is distributed in the hope that it will be useful,
 *    but WITHOUT ANY WARRANTY; without even the implied warranty of
 *    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
 *    Lesser General Public License for more details.
 */
package DirectedGraph;

import org.geotools.graph.path.Path;
import org.geotools.graph.structure.DirectedGraph;
import org.geotools.graph.structure.Graph;
import org.geotools.graph.structure.Graphable;
import org.geotools.graph.traverse.GraphTraversal;
import org.geotools.graph.traverse.GraphWalker;
import org.geotools.graph.traverse.basic.BasicGraphTraversal;
import org.geotools.graph.traverse.standard.DijkstraIterator;
import org.geotools.graph.traverse.standard.DijkstraIterator.EdgeWeighter;
import org.geotools.graph.traverse.standard.DijkstraIterator.NodeWeighter;
import org.geotools.graph.traverse.standard.DirectedDijkstraIterator;

/**
 * Calculates node paths in a graph using Dijkstra's Shortest Path Algorithm.
 * Dijsktras algorithm calculates a shortest path from a specefied node (the
 * source node of the underlying dijkstra iteration) to every other node in the
 * graph.
 *
 * @see DijsktraIterator
 * @author Justin Deoliveira, Refractions Research Inc, jdeolive@refractions.net
 *
 * @source $URL: http://svn.osgeo.org/geotools/trunk/modules/extension/graph/src/main/java/org/geotools/graph/path/DijkstraShortestPathFinder.java $
 */
public class DirectedDijkstraShortestPathFinder implements GraphWalker {

  /** Graphs to calculate paths for **/
  private DirectedGraph m_graph;

  /** Graph traversal used for the dijkstra iteration **/
  private GraphTraversal m_traversal;

  /** Underling Dijkstra iterator **/
  private DirectedDijkstraIterator m_iterator;

  /**
   * Constructs a new path finder.
   *
   * @param graph The graph to calculate paths for.
   * @param iterator The dijsktra iterator to used to calculate shortest paths.
   */
  public DirectedDijkstraShortestPathFinder(DirectedGraph graph, DirectedDijkstraIterator iterator) {
    m_graph = graph;
    m_iterator = iterator;
    m_traversal = new BasicGraphTraversal(graph, this, iterator);
  }

  /**
   * Constructs a new path finder.
   *
   * @param graph Graph to calculate paths for.
   * @param source Node to calculate paths from.
   * @param weighter Associates weights with edges in the graph.
   */
  public DirectedDijkstraShortestPathFinder(
    DirectedGraph graph, Graphable source, DirectedDijkstraIterator.EdgeWeighter weighter
  ) {
    this(graph,source,weighter,null);
  }

  /**
   * Constructs a new path finder.
   *
   * @param graph Graph to calculate paths for.
   * @param source Node to calculate paths from.
   * @param weighter Associates weights with edges in the graph.
   * @param nweighter Associates weights with nodes in the graph.
   */
  public DirectedDijkstraShortestPathFinder(
    DirectedGraph graph, Graphable source, DirectedDijkstraIterator.EdgeWeighter weighter, DirectedDijkstraIterator.NodeWeighter nweighter
  ) {
    m_graph = graph;
    //m_iterator = (DirectedDijkstraIterator) new DijkstraIterator(weighter,nweighter);
    m_iterator = new DirectedDijkstraIterator(weighter);
    m_iterator.setSource(source);
    m_traversal = new BasicGraphTraversal(graph, this, m_iterator);
  }

  /**
   * Performs the graph traversal and calculates the shortest path from
   * the source node to every other node in the graph.
   */
  public void calculate() {
    m_traversal.init();
    m_traversal.traverse();
  }

  /**
   * Returns a path <B>from</B> g <B>to</B> the source. If the desired path is
   * the opposite (from the source to g) can be used.
   *
   * @param g The start node of the path to be calculated.
   *
   * @see Path#riterator()
   *
   * @return A path from g to the source.
   */
  public Path getPath(Graphable g) {
    Path p = new Path();
    p.add(g);

    Graphable parent = g;
    while((parent = m_iterator.getParent(parent)) != null) p.add(parent);

    if (!p.getLast().equals(m_iterator.getSource())) return(null);

    return(p);
  }

  /**
   * Returns the cost associated with a node calculated during the graph
   * traversal.
   *
   * @param g The node whose cost is desired.
   *
   * @return The cost associated with the node.
   */
  public double getCost(Graphable g) {
    return(m_iterator.getCost(g));
  }

  public DijkstraIterator getIterator() {
    return(m_iterator);
  }

  public GraphTraversal getTraversal() {
    return(m_traversal);
  }

  /**
   * Does nothing except signal the traversal to continue.
   *
   * @see GraphWalker#visit(Graphable, GraphTraversal)
   */
  public int visit(Graphable element, GraphTraversal traversal) {
    return(GraphTraversal.CONTINUE);
  }

  /**
   * Does nothing.
   *
   * @see GraphWalker#finish()
   */
  public void finish() {}
}
